'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-11-03 13:48:33
'''
#
# @lc app=leetcode.cn id=174 lang=python3
#
# [174] 地下城游戏
#

# @lc code=start
from typing import List
class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        # 倒着考虑即可
        from sys import maxsize
        dp = [[0]*len(dungeon[0]) for _ in dungeon]
        for i in range(len(dungeon)-1, -1, -1):
            for j in range(len(dungeon[0])-1, -1, -1):
                minm = maxsize
                if i<len(dungeon)-1:
                    minm = min(minm, dp[i+1][j])
                if j<len(dungeon[0])-1:
                    minm = min(minm, dp[i][j+1])
                minm = minm if minm<maxsize else 0
                dp[i][j] = minm-dungeon[i][j] if minm-dungeon[i][j]>0 else 0
        print(dp)
        return dp[0][0]+1
# @lc code=end

if __name__ == "__main__":
    solution = Solution()
    dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
    print(solution.calculateMinimumHP(dungeon))